// https://leetcode.cn/problems/insert-interval/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        int left = newInterval[0];
        int right = newInterval[1];
        bool inserted = false;
        vector<vector<int>> ans;

        for (int i = 0; i < n; i++) {
            if (right < intervals[i][0]) {
                if (!inserted) {
                    ans.push_back({left, right});
                    inserted = true;
                }
                ans.push_back(intervals[i]);
                continue;
            }

            if (left > intervals[i][1]) {
                ans.push_back(intervals[i]);
                continue;
            }

            left = min(left, intervals[i][0]);
            right = max(right, intervals[i][1]);
        }

        if (!inserted) {
            ans.push_back({left, right});
        }
        return ans;
    }
};